package algorithm.leetcode.I1to100;

import java.util.Arrays;

/**
 * 插入区间
 *
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 */

public class Q57 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] res = new int[intervals.length + 1][2];
        int index = 0, resIndex = 0;

        // 分成三段考虑
        // 第一段,newInterval的左边全部大于intervals[i]的末尾
        while (index < intervals.length && intervals[index][1] < newInterval[0]) {
            res[resIndex++] = intervals[index++];
        }

        // 第二段,newInterval的始终与intervals[i]有重叠,即newInterval与intervals[i]的交集不为空,两个右端的较小值大于等于两个左端的较大值
        // 这段很容易出错
        while (index < intervals.length && Math.min(intervals[index][1], newInterval[1]) >= Math.max(intervals[index][0], newInterval[0])) {
            newInterval[0] = Math.min(intervals[index][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[index][1], newInterval[1]);
            index++;
        }
        res[resIndex++] = newInterval;

        // 第三段,newInterval的右边全部小于intervals[i]的开头
        while (index < intervals.length && intervals[index][0] > newInterval[1]) {
            res[resIndex++] = intervals[index++];
        }
        return Arrays.copyOf(res, resIndex);
    }

    public static void main(String[] args) {
        Q57 q57 = new Q57();
        int[][] ints = {{1,2},{3,5},{6,7},{8,10},{12,16}};
        int[] a = {4,8};
        System.out.println(Arrays.deepToString(q57.insert(ints, a)));
    }

}
